class Solution:
    def isValid(self, s: str) -> bool:
        stack = []
        dt = {
            '(': ')',
            '[': ']',
            '{': '}',
        }
        for i in range(len(s)):
            m = s[i]
            if m == '(' or m == '[' or m == '{':
                stack.append(m)
            elif len(stack) == 0 or m != dt[stack.pop()]: 
                return False
        return len(stack) == 0